package Medium;

import Structures.BinaryTree;
import Structures.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class LC1161 {
    public static int maxLevelSum(TreeNode root) {
        int levelNumber = 1, levelSum = 0, maxLevelSum = Integer.MIN_VALUE, retLevel = -1;

        Queue<TreeNode> queue = new LinkedList<>();
        int thisLevelCount = 0, nextLevelCount = 0;
        queue.add(root);
        thisLevelCount++;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            levelSum += node.val;
            thisLevelCount--;
            if (node.left != null) {
                queue.add(node.left);
                nextLevelCount++;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextLevelCount++;
            }

            if (thisLevelCount == 0) { // 开始遍历下一层
                if (levelSum > maxLevelSum) {
                    maxLevelSum = levelSum;
                    retLevel = levelNumber;
                }
                levelNumber++;
                levelSum = 0;
                thisLevelCount = nextLevelCount;
                nextLevelCount = 0;
            }
        }


        return retLevel;
    }

    public static void main(String[] args) {
        Integer[] elements = new Integer[]{989, null, 10250, null, null, 98693, -89388, null, null, null, null, null, null, null, -32127};
        TreeNode root = BinaryTree.constructBinaryTree(elements);
        System.out.println(maxLevelSum(root));
    }
}
